iT邦幫忙

2024 iThome 鐵人賽

DAY 24
0

題目

3043. Find the Length of the Longest Common Prefix
難度: 中等偏易

題意

給定兩整數陣列arr1arr2
arr1arr2之間所有整數對中,最長的相同前綴長度。
整數對: 一整數在arr1之中,另一整數arr2之中。
最長相同前綴: 將兩整數對以十進位字串表示時,相同的前綴。

範例1:
Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
整數對為100與1000,相同的前綴為100,其長度為3。

思路

需要反覆查找某東西在不在? 或某東西有幾個? 馬上聯想到用哈希表。

  1. 將其中一個整數陣列的所有前綴造出來,作為哈希表的鍵值。
  2. 將另一個整數陣列的所有前綴造出來,檢查哈希表中存不存在。若存在則更新最大的前綴長。

實作

因為只要查存不存在,無須知道前綴的排序,也無須知道前綴有幾個;所以選用unordered_set

class Solution
{
public:
    int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2)
    {
        // prefix integer
        unordered_set<int> us;

        // Build hash map for all prefixes in arr1
        for (auto num : arr1)
        {
            while (num)
            {
                us.insert(num);
                num /= 10;
            }
        }

        // Store the result for max length, so initialize to 0
        int res = 0;

        // Traverse all prefixes in arr2
        for (auto num : arr2)
        {
            while (num)
            {
                if (us.find(num) != us.end())
                {
                    res = max(res, (int)to_string(num).size());
                    // Early return since we only need the longest prefix
                    break;
                }
                num /= 10;
            }
        }

        return res;
    }
};

分析

若兩陣列的大小分別為M, N
時間複雜度: O(M + N),建表M * O(1),查表N * O(1)。
空間複雜度: O(max(M, N)),哈希表所需空間。

結果

Accepted
718/718 cases passed (269 ms)
Your runtime beats 67.25 % of cpp submissions
Your memory usage beats 89.16 % of cpp submissions (135.5 MB)

總結

這題是今年2月時的週賽題目,題目不會太難,很貼近實戰。
可惜當時的週賽,還刷得不夠多,哈希表不會用,只拿到TLE。
如今這題已經變反射題,可見菜就多練的重要性...

Time Submitted Status Runtime Memory Language
09/24/2024 22:31 Accepted 273 ms 135.7 MB cpp
02/20/2024 00:20 Accepted 424 ms 169.2 MB cpp
02/20/2024 00:18 Accepted 1124 ms 164.2 MB cpp
02/20/2024 00:17 Accepted 1369 ms 164.1 MB cpp
02/18/2024 11:00 Time Limit Exceeded N/A N/A cpp
02/18/2024 10:58 Time Limit Exceeded N/A N/A cpp
02/18/2024 10:56 Wrong Answer N/A N/A cpp

上一篇
[9/23] 除了字典裡的字串,最少字元數
下一篇
[9/25] 所有前綴出現的次數
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言